#include <stdio.h>
#include <stdlib.h>

#define m 3 // 3度树
#define MAXSIZE 20

typedef char datatype;
typedef struct node
{
    datatype data;
    int child[m];
    int parent;
} treenode;
typedef struct
{
    datatype data;
    int lev;
} levelnode;
treenode tree[MAXSIZE];
int root;
int length;
levelnode ltree[MAXSIZE];

/**
 * 将树的层号表示法转换成树的扩充孩子表示法
 * @return void
 */
void leveltotree(int length, levelnode ltree[], int *root, treenode tree[])
{
    int i, j, k;

    for (i = 0; i < length; i++)
    {
        for (j = 0; j < m; j++)
        {
            tree[i].child[j] = -1;
        }
    }

    *root = 0;
    tree[0].data = ltree[0].data;
    tree[0].parent = -1;

    for (i = 1; i < length; ++i)
    {
        tree[i].data = ltree[i].data;
        j = i - 1;

        if (ltree[i].lev > ltree[j].lev)
        {
            tree[i].parent = j;
            tree[j].child[0] = i;
        }
        else
        {
            while (ltree[i].lev <= ltree[j].lev)
            {
                j = tree[j].parent;
            }
            tree[i].parent = tree[j].parent;
            k = 0;
            while (tree[j].child[k] != -1)
            {
                k++;
            }
            tree[j].child[k] = i;
        }
    }
}

int main()
{
    int i, j, k;
    int root;
    int length;
    char ch;
    printf("请输入树的结点数：");
    scanf("%d", &length);
    getchar();
    printf("请输入树的结点信息：");
    for (i = 0; i < length; i++)
    {
        scanf("%c", &ch);
        ltree[i].data = ch;
        getchar();
        printf("请输入结点%c的层号：", ch);
        scanf("%d", &ltree[i].lev);
        getchar();
    }
    leveltotree(length, ltree, &root, tree);
    printf("树的扩充孩子表示法：\n");
    for (i = 0; i < length; i++)
    {
        printf("%c: ", tree[i].data);
        for (j = 0; j < m; j++)
        {
            if (tree[i].child[j] != -1)
            {
                printf("%c ", tree[tree[i].child[j]].data);
            }
        }
        printf("\n");
    }
    return 0;
}